Năm 1995, Corinna Cortes và Vladimir N. Vapnik đề xuất một ý tưởng mới cho phép thuật toán gán nhãn sai cho một số ví dụ luyện tập.[2] Nếu không tồn tại siêu phẳng nào phân tách được hai lớp dữ liệu, thì thuật toán lề mềm sẽ chọn một siêu phẳng phân tách các ví dụ luyện tập tốt nhất có thể, và đồng thời cực đại hóa khoảng cách giữa siêu phẳng với các ví dụ được gán đúng nhãn. Phương pháp này sử dụng các biến bù ξ i {\displaystyle \xi _{i}} , dùng để đo độ sai lệch của ví dụ x i {\displaystyle x_{i}}

y i ( w ⋅ x i − b ) ≥ 1 − ξ i 1 ≤ i ≤ n . ( 2 ) {\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1-\xi _{i}\quad 1\leq i\leq n.\quad \quad (2)}

Hàm mục tiêu có thêm một số hạng mới để phạt thuật toán khi ξ i {\displaystyle \xi _{i}} khác không, và bài toán tối ưu hóa trở thành việc trao đổi giữa lề lớn và mức phạt nhỏ. Nếu hàm phạt là tuyến tính thì bài toán trở thành:

min w , ξ , b { 1 2 ‖ w ‖ 2 + C ∑ i = 1 n ξ i } {\displaystyle \min _{\mathbf {w} ,\mathbf {\xi } ,b}\left\{{\frac {1}{2}}\|\mathbf {w} \|^{2}+C\sum _{i=1}^{n}\xi _{i}\right\}}

với điều kiện (với mọi i = 1 , … n {\displaystyle i=1,\dots n} )

y i ( w ⋅ x i − b ) ≥ 1 − ξ i ,         ξ i ≥ 0 {\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1-\xi _{i},~~~~\xi _{i}\geq 0}

Có thể giải bài toán trên bằng nhân tử Lagrange tương tự như trường hợp cơ bản ở trên. Bài toán cần giải trở thành:

min w , ξ , b max α , β { 1 2 ‖ w ‖ 2 + C ∑ i = 1 n ξ i − ∑ i = 1 n α i [ y i ( w ⋅ x i − b ) − 1 + ξ i ] − ∑ i = 1 n β i ξ i } {\displaystyle \min _{\mathbf {w} ,\mathbf {\xi } ,b}\max _{{\boldsymbol {\alpha }},{\boldsymbol {\beta }}}\left\{{\frac {1}{2}}\|\mathbf {w} \|^{2}+C\sum _{i=1}^{n}\xi _{i}-\sum _{i=1}^{n}{\alpha _{i}[y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1+\xi _{i}]}-\sum _{i=1}^{n}\beta _{i}\xi _{i}\right\}}

với α i , β i ≥ 0 {\displaystyle \alpha _{i},\beta _{i}\geq 0} .

Dạng đối ngẫu

Cực đại hóa (theo α i {\displaystyle \alpha _{i}} )

L ~ ( α ) = ∑ i = 1 n α i − 1 2 ∑ i , j α i α j y i y j k ( x i , x j ) {\displaystyle {\tilde {L}}(\mathbf {\alpha } )=\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i,j}\alpha _{i}\alpha _{j}y_{i}y_{j}k(\mathbf {x} _{i},\mathbf {x} _{j})}

với điều kiện (với mọi i = 1 , … , n {\displaystyle i=1,\dots ,n} )

0 ≤ α i ≤ C , {\displaystyle 0\leq \alpha _{i}\leq C,\,}

và

∑ i = 1 n α i y i = 0. {\displaystyle \sum _{i=1}^{n}\alpha _{i}y_{i}=0.}

Ưu điểm của việc dùng hàm phạt tuyến tính là các biến bù biến mất khỏi bài toán đối ngẫu, và hằng số C chỉ xuất hiện dưới dạng một chặn trên cho các nhân tử Lagrange. Cách đặt vấn đề trên đã mang lại nhiều thành quả trong thực tiễn, và Cortes và Vapnik đã nhận được giải Paris Kanellakis của ACM năm 2008 cho đóng góp này.[3] Các hàm phạt phi tuyến cũng được sử dụng, đặc biệt là để giảm ảnh hưởng của các trường hợp ngoại lệ, tuy nhiên nếu không lựa chọn hàm phạt cẩn thận thì bài toán trở thành không lồi, và việc tìm lời giải tối ưu toàn cục thường là rất khó.